package com.sunny.k_merge;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//直接利用指针比较
public class KMerge1 {

    public static void main(String[] args) {

        KMerge1 kMerge1 = new KMerge1();
        ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(1,3,5,7,8,9));
        ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(1,2,3,5,6,10,11));
        ArrayList<Integer> list3 = new ArrayList<>(Arrays.asList(1,1,3,3,8,8,9,10));
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        lists.add(list1);
        lists.add(list2);
        lists.add(list3);
        ArrayList<Integer> res = kMerge1.sort(lists);
        res.forEach(System.out::println);

    }

    public ArrayList<Integer> sort(ArrayList<ArrayList<Integer>> arr){
        ArrayList<Integer> list = new ArrayList<>();
        int[] ind = new int[arr.size()];
        int n = 0;
        for(int i=0;i<arr.size();i++){
            n += arr.get(i).size();
        }
        int cnt = 0;
        while (cnt < n) {
            int tmpInd = -1;
            int tmpNum = Integer.MAX_VALUE;
            for (int i = 0; i < arr.size(); i++) {
                if(ind[i] >= arr.get(i).size())
                    continue;
                if(tmpNum > arr.get(i).get(ind[i])){
                    tmpNum = arr.get(i).get(ind[i]);
                    tmpInd = i;
                }
            }
            ind[tmpInd]++;
            cnt++;
            list.add(tmpNum);
        }

        return list;
    }

}
